/*
 * Graph.hpp
 *
 *  Created on: 11 lis 2013
 *      Author: dawid.wysakowicz
 */

#ifndef GRAPH_HPP_
#define GRAPH_HPP_

#include <cstdint>
#include <cstddef>
#include <queue>
#include <tuple>

#include "Matrix.hpp"


namespace algorithm
{

class Graph
{
public:
	Graph(size_t verticesCount, size_t source, size_t target);
	common::Matrix<int> calculate();
	uint32_t getMaxFlow();
	void load(const std::vector<std::tuple<int, int, int>>&);

	virtual ~Graph();
private:
	bool bfs(const size_t matrixSize, const size_t startingVertex,
			const common::Matrix<int>& flows, std::vector<int>& path,
			std::vector<int>& residual, std::queue<size_t>& q);
	void extendFlow(const std::vector<int>& residual,
			const std::vector<int>& path, common::Matrix<int>& flows);

	size_t source_;
	size_t target_;
	uint32_t maxFlow_;
	common::Matrix<int> capacity_;
};

} /* namespace algorithm */

#endif /* GRAPH_HPP_ */
